#include <iostream>
#include <cstdlib>
#include <cassert>
#include <string>
using namespace std;

#include "Graph.h"
#include "Node.h"
#include "Algorithm.h"

#define NUMBER_OF_NODES 5

static Graph * g1, * g2, * g3;

static double percentage_of_coloured_nodes(int nb_couloured_nodes) {
    double a = (double) nb_couloured_nodes / (double) NUMBER_OF_NODES;
    return a * 100;
}

static void init() {
    //A simple 5-nodes graph
    g1 = new Graph("graph/graph_files/g1.txt");
    //A random 5-nodes graph
    g2 = new Graph(NUMBER_OF_NODES, 0.7);
    //A 3-coloriable 5-nodes graph
    g3 = new Graph(NUMBER_OF_NODES, 0.1, 3);
}

int main() {
    init();

    /***********************************************************/
    /** Our graph are saved on dot file for checking facility **/
    /***********************************************************/
    g1->saveOnDotFile("graph/dot_files/g1.dot");
    g2->saveOnDotFile("graph/dot_files/g2.dot");
    g3->saveOnDotFile("graph/dot_files/g3.dot");

    /******************************************************/
    /****************** Greedy algorithm ******************/
    /******************************************************/

    cout << "Greedy algorithm : " << endl;
    cout << "For g1 : " << greedy_algorithm(g1) << "-coloration found." << endl;
    cout << "For g2 : " << greedy_algorithm(g2) << "-coloration found." << endl;
    cout << "For g3 : " << greedy_algorithm(g3) << "-coloration found." << endl;
    cout << endl;

    /* The colouration of the algorithm */
    g1->saveOnDotFile("graph/dot_files/g1_greedy_colouration.dot");
    g2->saveOnDotFile("graph/dot_files/g2_greedy_colouration.dot");
    g3->saveOnDotFile("graph/dot_files/g3_greedy_colouration.dot");

    /******************************************************/
    /*************** Backtracking algorithm ***************/
    /******************************************************/
    int k = 3;
    int nb_coloured_nodes;
    init();

    cout << "Backtracking algorithm (with " << k << "-coloration) :" << endl;
    nb_coloured_nodes = backtracking_algorithm(g1, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g1 was coloured successfully." << endl;
    else
        cout << "g1 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    nb_coloured_nodes = backtracking_algorithm(g2, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g2 was coloured successfully." << endl;
    else
        cout << "g2 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    nb_coloured_nodes = backtracking_algorithm(g3, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g3 was coloured successfully." << endl;
    else
        cout << "g3 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    cout << endl;

    /* The colouration of the algorithm */
    g1->saveOnDotFile("graph/dot_files/g1_backtrack_colouration.dot");
    g2->saveOnDotFile("graph/dot_files/g2_backtrack_colouration.dot");
    g3->saveOnDotFile("graph/dot_files/g3_backtrack_colouration.dot");


    /******************************************************/
    /***************** No choice algorithm ****************/
    /******************************************************/

    init();

    cout << "No-choice algorithm (with " << k << "-coloration) :" << endl;

    nb_coloured_nodes = nochoice_algorithm(g1, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g1 was coloured successfully." << endl;
    else
        cout << "g1 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    nb_coloured_nodes = nochoice_algorithm(g2, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g2 was coloured successfully." << endl;
    else
        cout << "g2 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    nb_coloured_nodes = nochoice_algorithm(g3, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g3 was coloured successfully." << endl;
    else
        cout << "g3 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;
    cout << endl;

    /* The colouration of the algorithm */
    g1->saveOnDotFile("graph/dot_files/g1_nochoice_colouration.dot");
    g2->saveOnDotFile("graph/dot_files/g2_nochoice_colouration.dot");
    g3->saveOnDotFile("graph/dot_files/g3_nochoice_colouration.dot");

    /******************************************************/
    /*********** Optimized no choice algorithm ************/
    /******************************************************/

    init();

    cout << "Optimized no-choice algorithm (with " << k << "-coloration) :" << endl;

    nb_coloured_nodes = nochoice_algorithm_optimized(g1, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g1 was coloured successfully." << endl;
    else
        cout << "g1 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    nb_coloured_nodes = nochoice_algorithm_optimized(g2, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g2 was coloured successfully." << endl;
    else
        cout << "g2 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    nb_coloured_nodes = nochoice_algorithm_optimized(g3, k);
    if (nb_coloured_nodes == NUMBER_OF_NODES)
        cout << "g3 was coloured successfully." << endl;
    else
        cout << "g3 was partially coloured at " << percentage_of_coloured_nodes(nb_coloured_nodes) << "%" << endl;

    /* The colouration of the algorithm */
    g1->saveOnDotFile("graph/dot_files/g1_nochoice_opt_colouration.dot");
    g2->saveOnDotFile("graph/dot_files/g2_nochoice_opt_colouration.dot");
    g3->saveOnDotFile("graph/dot_files/g3_nochoice_opt_colouration.dot");

    /***************************************/
    /*********** SAT-reduction  ************/
    /***************************************/

    init();

    g1->saveOnCnfFile("graph/cnf_files/g1_minisat_file.cnf", k);
    g2->saveOnCnfFile("graph/cnf_files/g2_minisat_file.cnf", k);
    g3->saveOnCnfFile("graph/cnf_files/g3_minisat_file.cnf", k);

    /* Those are 3 samples minisat out files (note that we have
     * to call minisat manually every time for re-generate them */

    sat_colouring(g1, k, "graph/cnf_files/g1_minisat_file.out");
    g1->saveOnDotFile("graph/dot_files/g1_sat_colouration.dot");
    sat_colouring(g2, k, "graph/cnf_files/g2_minisat_file.out");
    g2->saveOnDotFile("graph/dot_files/g2_sat_colouration.dot");
    sat_colouring(g3, k, "graph/cnf_files/g3_minisat_file.out");
    g3->saveOnDotFile("graph/dot_files/g3_sat_colouration.dot");

    return EXIT_SUCCESS;
}
